package com.meterhuang;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayList;
import java.util.List;

/**
 * 回溯法
 *
 * 字符串子集搜索：
 * 给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合
 *
 * @author meterhuang
 * @date 2021/04/07 15:27
 */
@Slf4j
public class StringSearch {

	private static List<String> coll = new ArrayList<>();

	public static void main(String[] args) {
		String string = "a12bc!";
		String subStr = "";
		substr(subStr, string, 0);
		log.info("{}", coll);
	}

	/**
	 * 从头开始检索，遇到字母转变大小写，遇到其他字符跳过
	 * @param subStr
	 * @param string
	 * @param index
	 */
	private static void substr(String subStr, String string, int index) {
		if (index == string.length()) {
			coll.add(subStr);
			return;
		}
		char ch = string.charAt(index);
		if (Character.isLetter(ch)) {
			// 转大写
			char upper = Character.toUpperCase(ch);
			substr(subStr + upper, string, index + 1);
			//转小写
			char lower = Character.toLowerCase(ch);
			substr(subStr + lower, string, index + 1);
		} else {
			substr(subStr + ch, string, index + 1);
		}
	}
}
